﻿// MyProject.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
//公众号：程序员速成 ，内含一辈子都让你感激自己的优质视频教程，欢迎关注

#include <iostream>
#include <map>
#include <stack>
#include <vector>

#pragma warning (disable: 4996)

#ifdef _DEBUG   //只在Debug（调试）模式下
#ifndef DEBUG_NEW
#define DEBUG_NEW new(_NORMAL_BLOCK,__FILE__,__LINE__) //重新定义new运算符
#define new DEBUG_NEW
#endif
#endif

//#include <boost/type_index.hpp>
using namespace std;
//#pragma warning(disable : 4996) 

namespace _nmsp1
{		
	//小表达式（节点）的父类
	class Expression
	{
	public:
		Expression(int num, char sign) :m_dgb_num(num), m_dbg_sign(sign) {} //构造函数
		virtual ~Expression() {} //做父类时析构函数应该为虚函数。

	public:
		//解析语法树中的当前节点
		virtual int interpret(map<char, int> var) = 0; //map容器中的键值对用于保存变量名以及对应的值

	public:
		//以下两个成员变量是为程序跟踪调试时观察某些数据方便而引入
		int m_dgb_num; //创建该对象时的一个编号，用于记录本对象是第几个创建。
		char m_dbg_sign; //标记本对象类型，可能是个字符v代表变量（终结符表达式），也可以是个是个加减号（非终结符表达式）
	};

	//变量表达式（终结符表达式）
	class VarExpression :public  Expression
	{
	public:
		VarExpression(const char &key,int num,char sign):Expression(num,sign)//构造函数
		{
			m_key = key;
		}

		virtual int interpret(map<char, int> var)
		{
			return var[m_key]; //返回变量名对应的数值
		}
	private:
		char m_key; //变量名，本范例中诸如a,b,c,d都是变量名
	};

	//运算符表达式（非终结符表达式）父类
	class SymbolExpression :public Expression
	{
	public:
		//构造函数
		SymbolExpression(Expression* left, Expression* right, int num, char sign) :m_left(left), m_right(right), Expression(num, sign) {}
		Expression* getLeft() { return m_left; }
		Expression* getRight() { return m_right; }

	protected:
		//左右各有一个操作数
		Expression* m_left;
		Expression* m_right;
	};

	//加法运算符表达式（非终结符表达式）
	class AddExpression :public SymbolExpression
	{
	public:
		//构造函数
		AddExpression(Expression* left, Expression* right, int num, char sign) : SymbolExpression(left,right,num, sign) {}
		virtual int interpret(map<char, int> var)
		{
			//把步骤拆开写，方便理解和观察
			int value1 = m_left->interpret(var); //递归调用左操作数的interpret方法
			int value2 = m_right->interpret(var); //递归调用右操作数的interpret方法
			int result = value1 + value2;
			return result; //返回两个变量相加的结果
		}
	};
	//减法运算符表达式（非终结符表达式）
	class SubExpression :public SymbolExpression
	{
	public:
		//构造函数
		SubExpression(Expression* left, Expression* right, int num, char sign) : SymbolExpression(left, right, num, sign) {}
		virtual int interpret(map<char, int> var)
		{
			//把步骤拆开写，方便理解和观察
			int value1 = m_left->interpret(var); //递归调用左操作数的interpret方法
			int value2 = m_right->interpret(var); //递归调用右操作数的interpret方法
			int result = value1 - value2;
			return result; //返回两个变量相减的结果
		}
	};
	//----------------------------
	//分析-创建语法树（表达式树）
	Expression* analyse(string strExp) //strExp：要计算结果的表达式字符串，比如"a-b+c+d"。
	{
		stack< Expression*> expStack; //这里用到了栈这种顺序容器
		Expression* left = nullptr;
		Expression* right = nullptr;
		int icount = 1;
		for (size_t i = 0; i < strExp.size(); ++i) //循环遍历表达式字符串中每个字符
		{
			switch (strExp[i])
			{
			case '+':
				//加法运算符表达式（非终结符表达式）
				left = expStack.top(); //返回栈顶元素，左操作数
				++i;
				right = new VarExpression(strExp[i], icount++, 'v'); //'v'代表变量节点
				//在栈顶增加元素
				expStack.push(new AddExpression(left, right, icount++, '+'));//'+'代表是个加法运算符节点
				break;
			case '-':
				//减法运算符表达式（非终结符表达式）
				left = expStack.top(); //返回栈顶元素
				++i;
				right = new VarExpression(strExp[i], icount++, 'v');
				expStack.push(new SubExpression(left, right, icount++, '-'));//'-'代表是个减法运算符节点
				break;
			default:
				//变量表达式（终结符表达式）
				expStack.push(new VarExpression(strExp[i], icount++, 'v'));
				break;
			} //end switch
		} //end for
		Expression* expression = expStack.top(); //返回栈顶元素
		return expression;
	}

	void release(Expression* expression)
	{
		//释放表达式树的节点内存
		SymbolExpression* pSe = dynamic_cast<SymbolExpression*>(expression); //此处代码有优化空间（不使用dynamic_cast），留给大家思考
		if (pSe)
		{
			release(pSe->getLeft());
			release(pSe->getRight());
		}
		delete expression;
	}

}
namespace _nmsp2
{
	//表达式父类
	class Expression
	{
	public:
		~Expression() {} //做父类时析构函数应该为虚函数

	public:
		//解析语法树中的当前节点
		virtual string interpret() = 0;
	};

	//运动方向表达式（终结符表达式）
	class DirectionExpression :public Expression
	{
	public:
		DirectionExpression(const string& direction) //构造函数
		{
			m_direction = direction;
		}
		virtual string interpret()
		{
			if (m_direction == "up")
			{
				return "向上";
			}
			else if (m_direction == "down")
			{
				return "向下";
			}
			else if (m_direction == "left")
			{
				return "向左";
			}
			else if(m_direction == "right")
			{
				return "向右";
			}
			else
			{
				return "运动方向错";
			}
		}

	private:
		string m_direction; //运动方向：up、down、left、right：分别表示 上、下、左、右
	};

	//运动方式表达式（终结符表达式）
	class ActionExpression :public Expression
	{
	public:
		ActionExpression(const string& action) //构造函数
		{
			m_action = action;
		}
		virtual string interpret()
		{
			if (m_action == "walk")
			{
				return "行走";
			}
			else if (m_action == "run")
			{
				return "奔跑";
			}		
			else
			{
				return "运动方式错";
			}
		}

	private:
		string m_action; //运动方式：walk、run：分别表示  行走、奔跑
	};

	//运动距离表达式（终结符表达式）
	class DistanceExpression :public Expression
	{
	public:
		DistanceExpression(const string& distance) :m_distance(distance) {} //构造函数
		virtual string interpret()
		{
			return m_distance + "米";
		}

	private:
		string m_distance; //运动，用字符串表示即可
	};
	//“句子”表达式（非终结符表达式），“运动方向、运动方式、运动距离”构成
	class SentenceExpression :public Expression
	{
	public:
		SentenceExpression(Expression* directioin, Expression* action, Expression* distance) :
			m_direction(directioin), m_action(action), m_distance(distance) {} //构造函数

		Expression* getDirection()
		{
			return m_direction;
		}
		Expression* getAction()
		{
			return m_action;
		}
		Expression* getDistance()
		{
			return m_distance;
		}

		virtual string interpret()
		{
			return m_direction->interpret() + m_action->interpret() + m_distance->interpret();
		}

	private:
		Expression* m_direction; //运动方向
		Expression* m_action;   //运动方式
		Expression* m_distance;  //运动距离
	};

	//“和”表达式（非终结符表达式）
	class AndExpression :public Expression
	{
	public:
		AndExpression(Expression* left, Expression* right) :m_left(left), m_right(right) {} //构造函数
		Expression* getLeft() { return m_left; }
		Expression* getRight() { return m_right; }

		virtual string interpret()
		{
			return m_left->interpret() + "再" + m_right->interpret();
		}

	private:
		//左右各一个操作数
		Expression* m_left;
		Expression* m_right;
	};

	//分析-创建语法树（表达式树）
	Expression* analyse(string strExp) //strExp：要计算结果的表达式字符串，比如“left walk 15 and down run 20”
	{
		stack<Expression*> expStack;
		Expression* direction = nullptr; Expression* action = nullptr; Expression* distance = nullptr;
		Expression* left = nullptr;
		Expression* right = nullptr;

		//机器人运动控制命令之间使用空格来分隔的，所以用空格作为分隔字符来对整个字符串进行拆分
		char* strc = new char[strlen(strExp.c_str()) + 1];
		strcpy(strc, strExp.c_str());
		vector<string> resultVec; 
		char* tmpStr = strtok(strc, " "); //按空格来切割字符串
		while (tmpStr != nullptr)
		{
			resultVec.push_back(string(tmpStr));
			tmpStr = strtok(NULL, " ");
		}
		delete[] strc;
		for (auto iter = resultVec.begin(); iter != resultVec.end(); ++iter)
		{
			if ((*iter) == "and") //和
			{
				left = expStack.top(); //返回栈顶元素（左操作数）
				++iter;

				direction = new DirectionExpression(*iter); //运动方向
				++iter;
				action = new ActionExpression(*iter); //运动方式
				++iter;
				distance = new DistanceExpression(*iter); //运动距离

				right = new SentenceExpression(direction, action, distance);

				expStack.push(new AndExpression(left, right));
			}
			else
			{
				direction = new DirectionExpression(*iter); //运动方向
				++iter;
				action = new ActionExpression(*iter); //运动方式
				++iter;
				distance = new DistanceExpression(*iter); //运动距离

				expStack.push(new SentenceExpression(direction, action,distance));
			} //end if
		} //end for
		Expression* expression = expStack.top(); //返回栈顶元素
		return expression;
	}

	//释放内存release
	void release(Expression* expression)
	{
		//释放表达式树的节点内存
		SentenceExpression* pSE = dynamic_cast<SentenceExpression *>(expression);
		if (pSE)
		{
			release(pSE->getDirection());
			release(pSE->getAction());
			release(pSE->getDistance());
		}
		else
		{
			AndExpression *pAE = dynamic_cast<AndExpression*>(expression);
			if (pAE)
			{
				release(pAE->getLeft());
				release(pAE->getRight());
			}
		}
		delete expression;
	}

}

int main()
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);//程序退出时检测内存泄漏并显示到“输出”窗口
	
	//第21章 解释器（Interpreter）模式：解析器模式，行为型模式。适合对一些比较简单的文法结构进行分析（语言解释器）。
	//（1）一个用解释器模式编写的范例
	//一些变量，一个字母表示，a、b、c、d，值运行时指定。希望对这些变量进行加减法运算（不涉及乘除，考虑简单性）；
	//7、9、3、2，字符串“a-b+c+d”，“7-9+3+2” = 3; 
	//将这些规则表达为一个句子（实质就是如何将计算规则表达为一颗语法树【表达式树】），然后构建解释器来解释这个句子，这就是解释器模式所做的事。
	//非终结符表达式（树枝），终结符表达式（树叶）
	//语法树中的每个节点所属的类都会有一个叫做interpret的成员函数对本节点进行解释。

	//（2）引入解释器（Interpreter）模式
	//定于（实现意图）：定义一个语言的文法（语法规则），并建立一个解释器解释该语言中的句子。
	//当一个语言需要解释执行并且可以将该语言中的句子表示为一颗语法树的时候，就可以使用解释器模式。
	//4种角色：
	//a）AbstractExpression：抽象表达式，Expression类。
	//b）TerminalExpression：终结符表达式，VarExpression类。
	//c）NonterminalExpression：非终结符表达式，AddExpression类和SubExpression类。
	//d）Context：环境类/上下文类：varmap
	
	//优点：良好的灵活性和可扩展性。
	//缺点：适合实现小而简单的文法；执行效率不会太高；如果语法规则多，会产生大量的类，对于跟踪调试会产生诸多的不便。

	//（3）机器人运动控制范例
	//规定机器人的行为规则：
	//a）运动方向4个：上（up）、下（down）、左（left）、右（right）；
	//b）运动方式2个：行走（walk）、奔跑（run）；
	//c）机器人能够接受的终结符表达式有   运动方向、运动方式、运动距离（单位：米）。
	   //left walk 15 ：表示向左行走15米；
	   //down run 20：向下奔跑20米；
	//d)机器人能接受的非终结符表达式是“句子”，句子由“运动方向 运动方式 运动距离”构成。
	            //另一个非终结符表达式“and”，代表“和”的意思。比如
	   //left walk 15 and down run 20。











	/*
	string strExp = "a-b+c+d"; //将要求值的字符串表达式
	map<char, int> varmap;
	//下面是给字符串表达式中所有参与运算的变量一个对应的数值
	varmap.insert(make_pair('a', 7)); //类似于赋值语句a=7;
	varmap.insert(make_pair('b', 9)); //类似于赋值语句b=9;
	varmap.insert(make_pair('c', 3)); //类似于赋值语句c=3;
	varmap.insert(make_pair('d', 2)); //类似于赋值语句d=2;
	_nmsp1::Expression* expression = _nmsp1::analyse(strExp); //调用analyse函数创建语法树
	int result = expression->interpret(varmap);  //调用interpret接口求解字符串表达式的结果
	cout << "字符串表达式\"a-b+c+d\"的计算结果为：" << result << endl; //输出字符串表达式的结果

	_nmsp1::release(expression);
	*/

	string strExp = "left walk 15 and down run 20";
	_nmsp2::Expression* expression = _nmsp2::analyse(strExp); //调用analyse函数创建语法树
	cout << expression->interpret() << endl;

	//释放内存
	_nmsp2::release(expression);

	return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件

